package com.xiaoyg.algorithm;

public class IntersectionNode {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(4);
        ListNode node2 = new ListNode(1);
        ListNode node3 = new ListNode(8);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;


        ListNode node6 = new ListNode(5);
        ListNode node7 = new ListNode(0);
        ListNode node8 = new ListNode(1);
        node6.next = node7;
        node7.next = node8;
        node8.next = node3;


        ListNode result = getIntersectionNode1(node1, node6);
        System.out.println(result);

    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB){
        if (headA == null || headB == null) return null;
        ListNode pA = headA;
        ListNode pB = headB;
        while (pA != pB){
            //如果pA指针到了尾部，从B链表头开始
            if (pA == null){
                pA = headB;
            }else {
                pA = pA.next;
            }
            //如果pB到了尾部，从A链表头部开始
            if (pB == null){
                pB = headA;
            }else {
                pB = pB.next;
            }
        }
        return pA;
    }

    public static ListNode getIntersectionNode1(ListNode headA, ListNode headB){
        int l1=0 , l2 = 0, diff = 0;
        ListNode head1 = headA, head2 = headB;
        while (head1!=null){
            l1++;
            head1 = head1.next;
        }

        while (head2!=null){
            l2++;
            head2 = head2.next;
        }

        if (l1< l2){
            head1 = headB;
            head2 = headA;
            diff = l2-l1;
        }else {
            head1 = headA;
            head2 = headB;
            diff = l1-l2;
        }

        for(int i = 0; i< diff; i++){
            head1 = head1.next;
        }

        while (head1 != null && head2 != null){
            if (head1==head2){
                return head1;
            }
            head1 = head1.next;
            head2 = head2.next;
        }
        return null;
    }

    static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }
}
